"""
quicksort_v2
改进：和pivot值相等的元素有一半的概率交换，产生随机数决定是否交换
修改：将随机数生成由randint(0, 1)改为random.random()，提高效率，quicksort_v3.py已不再需要
"""
import random


def rand_partition_v2(sequence, p, r):
    i = random.randint(p, r)
    sequence[r], sequence[i] = sequence[i], sequence[r]
    x = sequence[r]
    i = p
    for j in range(p, r):
        # 如果当前元素等于x，就掷硬币决定是放在左侧还是放在右侧
        if sequence[j] < x or sequence[j] == x and random.random() < 0.5:
            sequence[i], sequence[j] = sequence[j], sequence[i]
            i += 1

    sequence[i], sequence[r] = sequence[r], sequence[i]
    return i


def _quicksort_v2(sequence, p, r):
    if p < r:
        q = rand_partition_v2(sequence, p, r)
        _quicksort_v2(sequence, p, q - 1)
        _quicksort_v2(sequence, q + 1, r)


def quicksort_v2(sequence):
    _quicksort_v2(sequence, 0, len(sequence) - 1)
